package com.cat.binaryTree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/k-th-largest-perfect-subtree-size-in-binary-tree/
 * @create 2025/9/13 15:36
 * @since JDK17
 */

public class Solution26 {
    List<Integer> list = new ArrayList<>();

    int[] f(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0}; // 深度，个数
        }
        int[] l = f(root.left);
        int[] r = f(root.right);
        int[] cur = new int[]{Integer.MIN_VALUE, Integer.MIN_VALUE};
        if (l[0] == r[0] && l[0] != Integer.MIN_VALUE) { // 深度一样
            cur[0] = l[0] + 1;
            cur[1] = 1 + r[1] + l[1];
            list.add(cur[1]);
        }
        return cur;
    }

    public int kthLargestPerfectSubtree(TreeNode root, int k) {
        f(root);
        Collections.sort(list);
        if (list.size() < k) {
            return -1;
        }
        return list.get(list.size() - k);
    }
}
